package codingforgreat.class16;

import java.util.HashSet;

//子数组和 缺少的最小正整数
public class Class02_SmallestUnFormedSum {
        //只包含正数
    public static int unformedSum1(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 1;
        }
        HashSet<Integer> set = new HashSet<>();
        process1(arr,0,0,set);
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < arr.length; i++) {
            min = Math.min(min,arr[i]);
        }
        for (int i = min + 1; i != Integer.MAX_VALUE ; i++) {
            if(!set.contains(i)){
                return i;
            }
        }
        return 0;
    }
    public static void process1(int[] arr,int i,int sum,HashSet<Integer> set){
        if(i == arr.length){
            set.add(sum);
            return;
        }
        process1(arr,i + 1,sum,set);
        process1(arr,i + 1,sum + arr[i],set);
    }
    public static int unformedSum2(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 1;
        }
        int sum = 0;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i != arr.length; i++) {
            sum += arr[i];
            min = Math.min(min, arr[i]);
        }
        // boolean[][] dp ...
        int N = arr.length;
        boolean[][] dp = new boolean[N][sum + 1];
        for (int i = 0; i < N; i++) {// arr[0..i] 0
            dp[i][0] = true;
        }
        dp[0][arr[0]] = true;
        for (int i = 1; i < N; i++) {
            for (int j = 1; j <= sum; j++) {
                dp[i][j] = dp[i - 1][j] || ((j - arr[i] >= 0) ? dp[i - 1][j - arr[i]] : false);
            }
        }
        for (int j = min; j <= sum; j++) {
            if (!dp[N - 1][j]) {
                return j;
            }
        }
        return sum + 1;
    }

}
